package com.veal98.bactrack;

import com.veal98.bean.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class LC113 {

    public static void main(String[] args) {

    }

    // 存储所有路径
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return res;
        }

        // 存储每条路径
        List<Integer> paths = new ArrayList<>();
        backtrack(root, targetSum, paths);

        return res;
    }

    // targetSum 随着路径中元素的增加而减少
    private void backtrack(TreeNode root, int targetSum, List<Integer> paths) {
        // 当前节点加入 paths
        paths.add(root.val);
        targetSum -= root.val;

        // 结束条件
        if (root.left == null && root.right == null && targetSum == 0) {
            // res.add(paths); error
            // Java 是按引用传递的。递归过程中 track 是在不断变化的，而我们需要的当前 track 的状态，所以需要在此处进行拷贝
            res.add(new ArrayList<>(paths));
            return ;
        }

        // 走左边
        if (root.left != null) {
            // 进入下一层解空间树
            backtrack(root.left, targetSum, paths);
            // 回溯
            paths.remove(paths.size() - 1);
        }

        // 走右边
        if (root.right != null) {
            // 进入下一层解空间树
            backtrack(root.right, targetSum, paths);
            // 回溯
            paths.remove(paths.size() - 1);
        }
    }


}
